package leetcode_121_140;

import DataStructure.Node;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

public class cloneGraph_133 {

    //缓存,复制前、复制后的节点关系
    private HashMap<Node, Node> nodeMap;

    /**
     * 克隆图
     */
    public Node cloneGraph(Node node) {
        //初始化缓存
        this.nodeMap = new HashMap<>();
        //判空
        if (node == null) {
            //过
            return null;
        }
        //递归收集所有节点,并复制节点本身,返回
        return collectNodeAndClone(node);
    }

    /**
     * 递归收集所有节点,并复制关系
     */
    private Node collectNodeAndClone(Node node) {
        //如果存在了
        if (this.nodeMap.containsKey(node)) {
            //获取复制后的节点并返回
            return this.nodeMap.get(node);
        }
        //复制节点
        Node cloneNode = new Node(node.val);
        //先记录二者关系
        this.nodeMap.put(node, cloneNode);

        //循环
        for (Node neighbor : node.neighbors) {
            //先复制起本身,并记录克隆的关系
            cloneNode.neighbors.add(collectNodeAndClone(neighbor));
        }
        //返回复制后的节点
        return cloneNode;
    }

}